package leetcode;

import java.util.Date;

/**
 * Created by 林剑 on 2016/10/28.
 */
public class wjk3 {
    static int min=Integer.MAX_VALUE;
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        wjk3 wjk3 = new wjk3();
        int a[] = {4,2,8};
        int b[] = {5,7,1};
        int n = a.length;
        int value = 0;
        int time = 0;
        for (int i =0;i<a.length;i++){
            time +=b[i];
        }
        boolean[] vis = new boolean[n];

        wjk3.dfs(a, b, n, vis, value, time);
        long end = System.currentTimeMillis();

        System.out.println(min);
        System.out.println(end-start);
    }
    public void dfs(int[] a,int b[],int n,boolean[] vis,int value,int time){
        if(time==0){
            min = min<value?min:value;
            return ;
        }
        for (int i =0;i<n;i++){
            if (!vis[i]){
                vis[i] = true;
                int temp = value+((time-a[i])>0?time-a[i]:0);
                if (min>temp||min==Integer.MAX_VALUE) {
                    dfs(a, b, n, vis, temp, time - b[i]);
                }
                vis[i] = false;
            }
        }
    }
}
